package com.arron.algorithm.leetcodetop100.回溯;

import java.util.*;

/**
 *
 *  动态规划解法 ： 分解问题
 * @see com.arron.algorithm.leetcodetop100.动态规划.单词拆分
 */
public class 单词拆分 {


    boolean flag;

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet<>();
        wordDictSet.addAll(wordDict);
        wordBreak(s, wordDictSet, 0);
        return flag;
    }


    public void wordBreak(String s, Set<String> wordDict, int start) {

        if (flag){
            return;
        }

        if (start == s.length()) {
            flag = true;
            return;
        }

        for (int len = 1; len <= s.length()-start; len++) {
            if (flag){
                break;
            }
            String prefix = s.substring(start, start + len);
            if (wordDict.contains(prefix)) {
                wordBreak(s, wordDict, start + len);
            }
        }
    }

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> strings = new ArrayList<>(Arrays.asList("lee", "code"));

        单词拆分 wordBreak = new 单词拆分();
        wordBreak.wordBreak(s, strings);
        System.out.println(wordBreak.flag);
    }


}
